package _剑指Offer;

/**
 * @ClassName: _56_1_数组中数字出现的次数
 * @Author: lerry_li
 * @CreateDate: 2021/05/17
 * @Description
 * 解法1：分组异或
 */
public class _56_1_数组中数字出现的次数 {

    public static void main(String[] args) {
        _56_1_数组中数字出现的次数 instance=new _56_1_数组中数字出现的次数();
        instance.singleNumbers(new int[]{4,1,4,6});
        System.out.println();
        instance.singleNumbers(new int[]{1,2,10,4,1,4,3,3});
    }

    /**
     * 解法1：分组异或 时间O(N) 空间O(1)
     * 思路：
     *      1）如果一个数组中只有1个数字出现了1次，其他数字都出现了2次，那么只需要把所有数字异或一遍即可
     *      2）想办法将数组分成2部分，每部分都包含1个仅出现1次的数字，其他数字都出现2次
     *
     * 为什么可以分组？
     *      由于2个相同数字异或的结果是0，如果2个数字不同，那么异或的结果必然不为0，即二进制某位为1；
     *      因此，可以根据某位为1的二进制位来划分数组，某位可以取最低位为1的二进制位。
     * 如何分组？
     *      遍历数组，看当前数字的某二进制位是0还是1，是0的为一组，是1的为一组
     *      1）两个相同的数字的对应位都是相同的，所以一个被分到了某一组，另一个必然被分到这一组；
     *      2）2个不同的数字必然分到不同组
     */
    public int[] singleNumbers(int[] nums) {
        //因为相同的数字异或为0，任何数字与0异或结果是其本身。
        //所以遍历异或整个数组最后得到的结果就是两个只出现一次的数字异或的结果：即 z = x ^ y
        int z = 0;
        for(int i : nums) z ^= i;
        //我们根据异或的性质可以知道：z中至少有一位是1，否则x与y就是相等的。
        //我们通过一个辅助变量m来保存z中哪一位为1.（可能有多个位都为1，我们找到最低位的1即可）。
        //举个例子：z = 10 ^ 2 = 1010 ^ 0010 = 1000,第四位为1.
        //我们将m初始化为1，如果（z & m）的结果等于0说明z的最低为是0
        //我们每次将m左移一位然后跟z做与操作，直到结果不为0.
        //此时m应该等于1000，同z一样，第四位为1.
        int m = 1;
        while((z & m) == 0) m <<= 1;
        //我们遍历数组，将每个数跟m进行与操作，结果为0的作为一组，结果不为0的作为一组
        //例如对于数组：[1,2,10,4,1,4,3,3]，我们把每个数字跟1000做与操作，可以分为下面两组：
        //nums1存放结果为0的: [1, 2, 4, 1, 4, 3, 3]
        //nums2存放结果不为0的: [10] (碰巧nums2中只有一个10，如果原数组中的数字再大一些就不会这样了)
        //此时我们发现问题已经退化为数组中有一个数字只出现了一次
        //分别对nums1和nums2遍历异或就能得到我们预期的x和y
        int x = 0, y = 0;
        for(int i : nums) {
            //这里我们是通过if...else将nums分为了两组，一边遍历一遍异或。
            //跟我们创建俩数组nums1和nums2原理是一样的。
            if((i & m) == 0) x ^= i;
            else y ^= i;
        }
        return new int[]{x, y};
    }
}
